//
// Created by REEJI2219 on 2024-09-18.
//
#include <iostream>
using namespace std;
//十字链表 存储系数矩阵
class Node {
public:
    int cal;//所在行
    int row;//所在列
    char data;//数据
    Node *right;//下一个指针
    Node *down;
    Node(int cal,int row,char data) {
        this->cal=cal;
        this->row = row;
        this->data =data;
        data = '-';
        right = nullptr;
        down = nullptr;
    }
};
//十字链表
class SparseMatrix {
public:
    int calCount;//所在行数
    int rowCount;//所在列数
    Node **rightArray;//所在列指针数组
    Node **downArray;//所在行指针数组
    SparseMatrix(int calCount,int rowCount) {
        this->calCount = calCount;
        this->rowCount = rowCount;
        //开辟内存数 calCount+rowCount
        downArray = new Node*[calCount];
        rightArray = new Node*[rowCount];
    }

    /**
     *
     * @param cal 所在行
     * @param row 所在列
     * @param data
     */
    void add(int cal,int row,char data) {
        Node *node = new Node(cal,row,data);
        //取出所在行
        Node *downHeader = downArray[cal];
        if(downHeader==nullptr) {
            downArray[cal] = node;
        }else {
            //进行大小判断，根据列进行判断，也就链表插入 ，此时是向后插入
            if(downHeader->row>node->row) {
                node->right = downHeader;
                downArray[cal] = node;
            }else {//找到最后一个比当前节点小的元素，查到后面
                insertRightNextNode(downHeader,node);
            }
        }
        //取出所在列
        Node *rightHeadr = rightArray[row];
        if(rightHeadr==nullptr) {
            rightArray[row] = node;
        }else {
            if(rightHeadr->cal>node->cal) {
                node->down = rightHeadr;
                rightArray[row] = node;
            }else {
                insertDownNextNode(rightHeadr,node);
            }
        }
    }
    void insertRightNextNode(Node* header,Node * node) {
        //前置设置为当前行
        Node* pre = header;
        //前面所在列大于node所在列，pre的下一个存在且也大于
        while( pre->row<node->row && pre->right!=nullptr && pre->right->row<node->row) {
            pre = pre->right;
        }
        //此时 要么为最后一个，要么为 当前节点处于pre之后。处于pre.right之前，在这两者中间插入
        // printf("before P %d %d %c ,N %d %d %c | \n" ,pre->cal,pre->row,pre->data,node->cal,node->row,node->data);
        node->right = pre->right;
        // printf("end P %d %d %c ,N %d %d %c | \n" ,pre->cal,pre->row,pre->data,node->cal,node->row,node->data);
        pre->right = node;
    }

    void insertDownNextNode(Node* header,Node * node) {
        Node* pre = header;
        //找到比pre 小，比next大的节点
        while(pre->cal<node->cal && pre->down!=nullptr && pre->down->cal<node->cal) {
            pre = pre->down;
        }
        // printf("before P %d %d %c ,N %d %d %c | \n" ,pre->cal,pre->row,pre->data,node->cal,node->row,node->data);
        node->down = pre->down;
        // printf("end P %d %d %c ,N %d %d %c | \n" ,pre->cal,pre->row,pre->data,node->cal,node->row,node->data);
        pre->down = node;
    }
    //按照行遍历
    void printByCal() {
        for(int i=0;i<calCount;i++) {
            Node * header = downArray[i];
            while(header!=nullptr) {
                printf("%d %d %c |",header->cal, header->row,header->data);
                header = header->right;
            }
            printf("\n");
        }
    }
    void printByRow() {
        for(int i=0;i<rowCount;i++) {
            Node * header = rightArray[i];
            while(header!=nullptr) {
                printf("%d %d %c |",header->cal, header->row,header->data);
                header = header->down;
            }
            printf("\n");
        }
    }

};

// int main(int argc, char *argv[]) {
//     SparseMatrix *matrix = new SparseMatrix(4,5);
//     matrix->add(3,1,'a');
//     matrix->add(3,0,'d');
//     matrix->add(3,4,'c');
//     matrix->add(0,4,'x');
//     matrix->add(0,1,'s');
//     matrix->add(2,1,'n');
//     matrix->add(2,3,'q');
//     matrix->add(2,0,'p');
//     matrix->printByCal();
//     printf("---------------------\n");
//     matrix->printByRow();
//
// }
